package labuladong.BFS;


import java.util.HashSet;
import java.util.Queue;

/**
 * bfs模板
 */
public class muban {
    public static void main(String[] args) {
        bfs(0, 1);
    }

    // 计算从起点 start 到终点 target 的最近距离
    public static int bfs(int start, int target) {
        Queue q = null;   // 核⼼数据结构
        HashSet visited = null;    // 避免⾛回头路

        q.offer(start);   // 将起点加入队列
        visited.add(start);
        int step = 0; // 记录扩散步数

        while (!q.isEmpty()) {
            int size = q.size();
            // 将当前队列向四周扩散
            for (int i=0; i<size; i++) {
                int cur = (int) q.poll();
                // 划重点：这⾥判断是否到达终点
                if (cur == target) {
                    return step;
                }
                // 将 cur 的相邻节点加⼊队列
                for (int x:adj(cur)) {
                    if(!visited.contains(x )) {
                        q.offer(x);
                        visited.add(x);
                    }
                }
                return step;
            }
        }
        return -1;
    }

    // cur的相邻节点
    public static int[] adj(int cur) {
        int[] arr = {1, 2, 3, 4};
        return arr;
    }
}
